#include <iostream>
#include <algorithm>
#include <vector>

#define v first
#define w second

using namespace std;

typedef pair<int, int> PII;

const int N = 70, M = 32010;

int n, m;
PII master[N];
vector<PII> servant[N];
int f[M];

int main() {
    cin >> m >> n;
    
    for (int i = 1; i <= n; ++ i) {
        int v, w, q;
        cin >> v >> w >> q;
        w *= v;
        if (!q) master[i] = {v, w};
        else servant[q].push_back({v, w});
    }
    
    for (int i = 1; i <= n; ++ i) {
            auto &ms = master[i];
            auto &sv = servant[i];
            
            for (int j = m; j >= 0; -- j) {
                for (int k = 0; k < 1 << sv.size(); ++ k) {
                    int v = ms.v, w = ms.w;
                    for (int u = 0; u < sv.size(); ++ u) 
                        if (k >> u & 1) {
                            v += sv[u].v;
                            w += sv[u].w;
                        }
                    if (j >= v) f[j] = max(f[j], f[j - v] + w);
                }
            }
        }
    
    cout << f[m] << endl;
    
    return 0;
}